package 双周赛;

import java.util.ArrayList;
import java.util.List;

/**
 *
 */
public class 第109场双周赛 {

    public static void main(String[] args) {

        System.out.println(sortVowels("lEetcOde"));

    }

    /**
     * 1，使用数组标记某个字母是元音
     * 2，使用位运算 |32 将元音转小写进行判断是否元音
     */
    public static String sortVowels(String s) {
        char[] chars = s.toCharArray();
        boolean[] isVowel = new boolean[26];
        for (char c : "aeiou".toCharArray()) {
            isVowel[c - 'a'] = true;
        }
        List<Character> list = new ArrayList<>();
        for (char c : chars) {
            if (isVowel[(c | 32) - 'a']) {
                list.add(c);
            }
        }
        list.sort((a, b) -> a - b);
        int idx = 0;
        for (int i = 0; i < chars.length; i++) {
            if (isVowel[(chars[i] | 32) - 'a']) {
                chars[i] = list.get(idx);
                idx++;
            }
        }
        return new String(chars);
    }

    /**
     * 动态规划
     * 1，子问题
     * dp[i] 表示选 i 的最大得分是多少
     * 2，状态转移方程
     * dp[i] 只与 dp[0,i-1] 中偶数的最大得分和奇数的最大得分相关
     * 注意：
     * 1，最小值不一定就是 0 ，因为可能需要 - x ，nums[0] 要先判断，否则初始值为 Integer.MIN_VALUE，而 num[i]
     * 较小，算出来的得分是负数
     * 2，偶数的最大得分就是顺序遍历最后一个偶数的最大得分，奇数一样
     */
    public long maxScore(int[] nums, int x) {
        long oddMaxScore = Integer.MIN_VALUE, evenMaxScore = Integer.MIN_VALUE;
        if (nums[0] % 2 == 0) {
            evenMaxScore = nums[0];
        } else {
            oddMaxScore = nums[0];
        }

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                evenMaxScore = Math.max(nums[i] + evenMaxScore,
                        nums[i] + oddMaxScore - x);
            } else {
                oddMaxScore = Math.max(nums[i] + oddMaxScore,
                        nums[i] + evenMaxScore - x);
            }
        }
        return Math.max(oddMaxScore, evenMaxScore);
    }

}
